#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
//解法1 固定宽度 超时
int largestRectangleArea1(vector<int>& heights) {
    return 0;
}

//解法1 固定高度 超时
int largestRectangleArea2(vector<int>& heights) {
    int n = heights.size();
    int ans = 0;
    //确定边界
    for (int mid = 0; mid < n; ++mid) {
        int height = heights[mid];

        //确定左右边界
        int left = mid, right = mid;
        while (left>=0 && heights[left]>=height)left--;
        while (right<n && heights[right]>=height) right++;

        ans = max(ans, (right-left-1)*height);
    }
    return ans;

}

//单调栈 双向
int largestRectangleArea3(vector<int>& heights) {
    int n = heights.size();
    int ans = 0;
    vector<int> left(n, -1);
    stack<int> st1;
    for (int i = n-1; i >=0 ; i--) {
        while (!st1.empty() && heights[i]<heights[st1.top()]){
            left[st1.top()] = i;
            st1.pop();
        }
        st1.push(i);
    }


    vector<int> right(n, -1);
    stack<int> st2;
    for (int i = 0; i <n ; i++) {
        while (!st2.empty() && heights[i]<heights[st2.top()]){
            right[st2.top()] = i;
            st2.pop();
        }
        st2.push(i);
    }

    for (int mid = 0; mid < n; ++mid) {
        int height = heights[mid];

        ans = max(ans, (right[mid]-left[mid]-1)*height);
    }
    return ans;

}

// 枚举高 + 单调栈优化 + 一次遍历
int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();

    vector<int> left(n);
    vector<int> right(n, n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && heights[i] <= heights[st.top()]) {
            right[st.top()] = i;
            st.pop();
        }
        left[i] = (st.empty() ? -1 : st.top());
        st.push(i);
    }

    int ans = 0;
    for (int mid = 0; mid < n; mid++) {
        int height = heights[mid];
        int width = right[mid] - left[mid] - 1;
        ans = max(ans, height * width);
    }

    return ans;
}

int main(){
    vector<int> heights = {2,1,5,6,2,3};
    largestRectangleArea(heights);
    return 0;
}
